package 剑指Offer._5160;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/11/16 14:10
 * 0～n-1中缺失的数字
 * 一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。
 * 在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
 * 算法：位运算   二分查找
 * 因为数组是有顺序的，所以可以使用二分查找
 * 如果第 i 位缺失了，那么 i 与第 i 位的元素不一样，这个可以作为条件
 */
public class _53II {

    public int missingNumber_weiyunsuan(int[] nums) {
        int ans = 0;
        int len = nums.length;
        for (int i = 0; i <= len; i++) ans ^= i;
        for (int i = 0; i < len; i++) ans ^= nums[i];
        return ans;
    }

    public int missingNumber_binary(int[] nums) {
        int l = 0, r = nums.length - 1;
        while (l <= r) {
            int mid = l + r >> 1;
            if (nums[mid] == mid) l = mid + 1;
            else r = mid - 1;
        }
        return l;
    }

}
